package binarySearch;

/*
* 二分查找
* */
public class BinarySearch {

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9};
        int i = temp(nums, 0, 8, 1);
        System.out.println("索引"+i);

    }



    public static int temp(int[] nums , int left , int right, int target){
        System.out.println("test");

        if (left >  right || target < nums[left] || target > nums[right]){
            return -1;
        }
        int mid = (left + right)/2;
        if (target > nums[mid]){
            return temp(nums, mid + 1, right, target);
        }else if(target < nums[mid]){
            return temp(nums, left, mid-1, target);
        }else {
           return mid;
        }
    }

    //在数组nums找到比target大的最小数字
    public static int binarySearchFirstOccuranceOfTarget(int[] nums,int target){
        int left = 0,right = nums.length;
        while(left < right){
            int mid = left + (right -left)/2;//防止下表过大 数据溢出
            if (nums[mid] == target){
                right = mid;
            }else if(nums[mid] > target){
                //目标左边 缩紧右侧边界
                right = mid;
            }else if (nums[mid] < target){
                //目标在右侧
                left = mid +1;
            }
        }
        //如果有target 返回下表  如果无此target返回比target小的最大数
        return left;
    }

    public static int binarySearchFirstOccuranceFirstTargetPlus(int[] nums,int target){
       int left =0,right = nums.length;
       while(left < right){
           int mid = left + (right - left)/2;
           if (nums[mid] < target){
               left = mid+1;
           }else{
               right = mid;
           }
       }
       return left;
    }


    //细节 如果存在重复元素  我只想找最左侧或者最右侧的下标(细节很重要)

    //细节一 找到左侧边界值 此时查找区间[left,right)
    public static int binarySearchLeftDemo(int[] nums,int target){
        if (nums == null)return -1;
        int left =0,right= nums.length;
        while(left < right){
            int mid = left + (right - left)/2;//防止mid下标溢出
            if (nums[mid] == target){
                right = mid;//细节 如果找到target 收缩右侧
            }else if(nums[mid] > target){
                //目标在左侧
                right = mid;
            }else if(nums[mid] < target){
                //目标在右侧
                left = mid+1;
            }
        }
        return left;
    }

    //细节二 查找右侧边界
    public static int binarySearchRight(int[] nums ,int target){
        if (nums.length == 0)return -1;
        int left =0,right = nums.length;
        while(left < right){
            int mid = left +(right-left)/2;
            if (nums[mid] == target){
                left = mid+1;
            }else if(nums[mid] > target){
                //目标在左侧
                right = mid;
            }else if (nums[mid] < target){
                //目标在右侧
                left = mid+1;
            }
        }
        return right-1;//细节
    }
}
